package com.zsj.Tree;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/6/2 17:53
 * @description 前缀树
 */
public class PrefixTree {

    public static class TrieNode {
        public int pass;
        public int end;
        //拓展 中文字符或者其它字符 我们可以使用哈希表的方式
        //HashMap<Character,Node> nexts;//这个character表示字符 node表示下级
        public TrieNode[] nexts;

        public TrieNode() {
            pass = 0;
            end = 0;
            nexts = new TrieNode[26];
        }
    }

    public static class Trie {
        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            if (word == null) {
                return;
            }
            char[] chars = word.toCharArray();
            TrieNode node = root;
            node.pass++;//标识有节点经过了
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';//计算出应该记录的位置
                if (node.nexts[index] == null) {
                    //如果没有这条路 新建
                    node.nexts[index] = new TrieNode();
                }
                //使用节点
                node = node.nexts[index];
                //节点经过了
                node.pass++;
            }
            node.end++;
        }

        //查询这个字符加入过几次  我们只需要查询end的次数
        public int search(String word) {
            if (word == null) {
                return 0;
            }
            char[] chars = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.end;
        }

        //查询所有字符串中 有多少个字符以这个字符为前缀的 查pass就可以
        public int prefixNumber(String word) {
            if (word == null) {
                return 0;
            }
            char[] chars = word.toCharArray();
            TrieNode node = root;
            int index = 0;
            for (int i = 0; i < chars.length; i++) {
                index = chars[i] - 'a';
                if (node.nexts[index] == null) {
                    return 0;
                }
                node = node.nexts[index];
            }
            return node.pass;
        }

        //删除
        public void delete(String word) {
            //搜索树中出现过吗？确保出现过才能删除
            if (search(word) != 0) {
                char[] chars = word.toCharArray();
                TrieNode node = root;
                node.pass--;
                int index = 0;
                for (int i = 0; i < chars.length; i++) {
                    index = chars[i] - 'a';
                    if (--node.nexts[index].pass == 0) {
                        //如果没有pass 就代码没有节点经过他
                        //将它的所有后节点全部释放掉
                        node.nexts[index] = null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }
    }

}
